‎In this paper‎, ‎we calculate the expected values of the first and second Zagreb indices‎, ‎denoted as $\textbf{E}\left(M_1\right)$ and $\textbf{E}\left(M_2\right)$ respectively‎, ‎as well as the expected value of the forgotten index‎, ‎$\textbf{E}\left(F\right)$‎, ‎for two models of Random bipartite graphs‎. ‎To evaluate our findings‎, ‎we establish the growth rate by demonstrating that for a Random bipartite graph $G$ of order $n$ in either model‎, ‎the expected value of $M_1(G)$ is $O\left( n^3 \right)$‎. ‎Furthermore‎, ‎we prove that the expected values of $M_2(G)$ and $F(G)$ are both $O\left( n^4 \right)$‎.

Given a graph G, a graph F is said to be Ramsey for G if in every edge coloring of F with two colors, there exists a monochromatic copy of G. The minimum number of edges of a graph F which is Ramsey for G is called the size-Ramsey number of G and is denoted by ^r(G). In 1983, Beck gave a linear upper bound (in terms of n) for ^r(Pn), where Pn is a path on n vertices, giving a positive answer to a question of Erd}os. After that, different approaches were attempted by several authors to reduce the upper bound for ^r(Pn) for sufficiently large n and most of these approaches are based on the classic models of Random graphs. Also, Haxell and Kohayakama in 1994 proved that the size Ramsey number of the cycle Cn is linear in terms n, however the Szemeredi's regularity lemma is used in their proof and so no speci c constant coefficient is provided. Here, we provide a method to obtain an upper bound for the size Ramsey number of a graph using good expander graphs such as Ramanujan graphs. In particular, we give an alternative proof for the linearity of the size Ramsey number of paths and cycles. Our method has two privileges in compare to the previous ones. Firstly, it proves the upper bound for every positive integer n in comparison to the Random graph methods which needs n to be sufficiently large. Also, due to the recent explicit constructions for bipartite Ramanujan graphs by Marcus, Spielman and Srivastava, we can constructively  nd the graphs with small sizes which are Ramsey for a given graph. We also obtain some results about the bipartite Ramsey numbers.

A graph G is said to be H-free if G does not contain H as an induced subgraph. Let S 2 n(m) be a variation of double star S 2 n obtained by adding m(≤ n) disjoint edges between the pendant vertices which are at distance 3 in S 2 n. A graph having integer eigenvalues for its signless Laplacian matrix is known as a Q-integral graph. The Q-spectral radius of a graph is the largest eigenvalue of its signless Laplacian. Any connected Q-integral graph G with Q-spectral radius 7 and maximum edge-degree 8 is either K1, 4K2 or contains S 2 4 (0) as an induced subgraph or is a bipartite graph having at least one of the induced subgraphs S 2 4 (m), (m = 1, 2, 3). In this article, we improve this result by showing that every connected Q-integral graph G having Q-spectral radius 7, maximum edge-degree 8 is always bipartite and S 2 4 (3)-free.

For any given $n,k \in \mathbb{N}$ with $ 2k < n, $ the $bipartite\ Kneser \ graph$ $H(n, k)$ is defined as the graph whose vertex set is the family of $k$-subsets and ($n-k$)-subsets of $[n] = \{1, 2,\dots, n\}, $ in whichany two vertices are adjacent if and only if one of them is a subset of the other.In this paper, we study some algebraic properties of the bipartite Kneser graph $H(n, k)$. In particular, we determine the values of $n,k$, for which the bipartite Knesergraph $H(n,k)$ is a Cayley graph.

Let G = (V, E) be a simple graph. An edge labeling f: E®{0, 1} induces a vertex labeling f+: V ® Z2 defined by f+ (v) º S uvÎE f (uv) (mod 2) for each v Î V , where Z2 = {0, 1} is the additive group of order 2. For i Î {0, 1}, let ef (i) = ÷f-1 (i)÷ and vf (i) = ÷(f+) -1(i)÷. A labeling f is called edge-friendly if ÷ef (1) - ef (0)÷ £ 1. If (G) = vf (1) - vf (0) is called the edge-friendly index of G under an edge-friendly labeling f. Extreme values of edge-friendly index of complete bipartite graphs will be determined.

Please click on PDF to view the abstract.

In this paper, we construct a new class of integral bipartite graphs (not necessarily trees) with large even diameters. In fact, for every nite set A of positive integers of size k we construct an integral bipartite graph G of diameter 2 k such that the set of positive eigenvalues of G is exactly A. This class of integral bipartite graphs has never found before.

Let G be a bipartite graph. In this paper we consider the two kind of location problems namely p-center and p-median problems on bipartite graphs. The p-center and p-median problems asks to find a subset of vertices of cardinality p, so that respectively the maximum and sum of the distances from this set to all other vertices in G is minimized. For each case we present some properties to find exact solutions.

A graph is called supermagic if there is a labeling of edges where the edges are labeled with consecutive distinct positive integers such that the sum of the labels of all edges incident with any vertex is constant. A graph G is called degree-magic if there is a labeling of the edges by integers 1, 2, ..., |E (G) | such that the sum of the labels of the edges incident with any vertex v is equal to (1+|E (G) |) deg (v) /2.Degree-magic graphs extend supermagic regular graphs. In this paper we find the necessary and sufficient conditions for the existence of balanced degree-magic labelings of graphs obtained by taking the join, composition, Cartesian product, tensor product and strong product of complete bipartite graphs.